238. 除自身以外数组的乘积

Similar Question

Solution Tips

方案: 前缀和 + 后缀和

前缀和后缀和要根据题意初始化, 不能太死板了, 这里其实是不包含 i 自身的, 搞得边界情况最后自己都弄不懂了

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {

    // 同时使用前缀和与后缀和 answer[i] = sums[i] + sums[i+2]
    // 同时预留两边的边界, 所以是 + 2
    // const sums = new Array(nums.length+2).fill(0)
    // for (let i = 0; i < nums.length; i++) {
    //     sums[i + 1] = sums[i] + sums[i + 2]
    // }
    const res = [];
    const sufSums = new Array(nums.length + 1).fill(1)
    for (let i = nums.length - 1; i >= 0; i--) {
        const num = nums[i];
        sufSums[i] = sufSums[i + 1] * num
        // 本来以为减少一次n会快一点, 结果反而更慢了
        // 可能是因为 unshift 太慢了
        // res.unshift(preSums[i] * sufSums[i + 1])
    }

    // 没有办法一次遍历计算出前后缀, 分开来就好了
    const preSums = new Array(nums.length + 1).fill(1)
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        preSums[i+1] = preSums[i] * num
        res.push(preSums[i] * sufSums[i+1])
    }


    // 计算 answer 数组
    // const res = [];
    // for (let i = 0; i < nums.length; i++) {
    //     res.push(preSums[i] * sufSums[i + 1])
    // }
    return res;
};

console.log(productExceptSelf([1,2,3,4]))

优化空间复杂度: answer 直接使用 presum 已经创建好的数组, sufSum 也不用创建了, 直接乘算就行